This invention relates to wireless telecommunication systems. More particularly, and not by way of limitation, the invention is directed to an arrangement and method for contention-based multi-access for user terminals operating over wireless, fading, dispersive channels in a wireless communication system.
In wireless packet data systems, many user terminals (UTs) may attempt to transmit packets on an uplink channel to an access point (AP). The uplink multi-access scheme in most wireless systems is reservation based, i.e., each UT wishing to transmit on the uplink must first request the AP to schedule resources for it on the uplink. Once the AP has assigned resources for the requesting UT, and once this assignment has been communicated to the UT, the UT is allowed to transmit on the uplink using the assigned resources.
In some wireless systems, the UT can request uplink resources using a contention-based multi-access scheme (typically a slotted Aloha scheme). A good example of such an approach is WiMax (802.16) on the uplink. In WiMax, the uplink channel utilizes orthogonal frequency division multiplexing (OFDM), and therefore, the uplink channel is divided into many sub-carriers. Furthermore, the channel is divided into non-overlapping slots in the time domain. WiMax defines contention-based request channels where each channel consists of M contiguous sub-carriers. Assuming that the wireless channel does not change over these M sub-carriers, WiMax defines M orthogonal codes on each request channel. With M orthogonal codes, M UTs (each using a different one of these orthogonal codes) can simultaneously transmit requests to the AP on each slot. Each UT wishing to transmit on this request channel chooses one code among the possible M codes randomly; hence, it is possible that two transmitting UTs will chose the same code and this will lead to a collision and loss of the transmitted packets.
In effect, WiMax creates M parallel, contention-based, multi-access channels for transmission of requests. Each of these request channels essentially implements a slotted Aloha protocol. Each UT can transmit a packet at will on any slot using one of these M parallel channels, and as long as no other UT simultaneously transmits on the same slot and on the same one of the M request channels, the request will be received correctly by the AP.
The main shortcoming of a reservation-based multi-access scheme is extra delay incurred by each packet transmitted on the uplink channel. The process of requesting a resource reservation by the UT, and subsequently communicating the reservation from the AP to the UT adds extra delay between the time a packet arrives at the UT and the time the packet is transmitted on the uplink.
A problem with using only contention-based request channels (for example, WiMax) is that the UTs can only use the contention-based multi-access for making reservations. This approach does not allow for transmitting the actual data packets in contention mode. Thus, in this approach, the data packets still incur a delay due to the process of requesting resource reservations and communicating the reservations back to the UTs.
The contention-based request channels in WiMax are designed so that the UT can transmit only a very few bits of information to the AP. In WiMax there is no mechanism for setting the information rate on the contention-based request channels because data packets are not transmitted on this channel.
In wireline systems, Ethernet is by far the most commonly used contention-based, multi-access method. Ethernet uses a form of Carrier Sense Multiple Access (CSMA) in which each node wishing to transmit first listens to what is being transmitted on the channel for a while (carrier sensing), and if this node does not hear any other node transmitting, it would proceed to transmit on the channel. Unfortunately, CSMA is not well suited for wireless applications. In wireless systems, mobile stations typically transmit and receive (i.e., listen) on different frequencies; hence, it is not possible for most wireless mobile stations to listen to the transmissions of other mobile stations. Furthermore, due to line-of-sight and other restrictions in wireless environments, dispersed mobile stations would probably not be able to hear all of the other mobile stations transmitting to the AP. The AP may be able to receive a signal from a given transmitting mobile station, while this signal is not receivable (due to an obstruction) at another mobile station. This is typically referred to as the “hidden node problem”, and it renders CSMA unsuitable for wireless environments. See, D. Bertsekas and R. Gallager, Data Networks, Second Edition, 1992, Prentice-Hall Inc., New Jersey.
Another well-known approach for implementing contention-based multi-access in wireless environments is to transmit data packets (not just access requests) using the slotted Aloha protocol. Slotted Aloha is a single-packet, contention-based approach meaning only one packet can get through per slot. If more than one UT attempts to transmit in a particular slot, nothing gets through. In such a system, each UT selects some random slot following the arrival of a data packet for transmission of the packet to the AP. As long as no other UTs transmit on the same slot, the AP correctly receives the data packet. If one or more UTs transmit on the same slot, the AP does not receive any packets correctly. It is well known, that the maximum number of correctly received packets-per-slot with this approach is 1/e˜0.36. See, D. Bertsekas and R. Gallager, Data Networks, Second Edition, 1992, Prentice-Hall Inc., New Jersey. In other words, the maximum throughput with slotted Aloha is 0.36 (packets/slot). Similarly, the maximum offered load that can be supported with slotted Aloha at finite packet delay is 0.36 packets/slot. With slotted Aloha, as long as the number of new packet arrivals per slot is significantly below 0.36, the packet delay is quite low. However, this leads to low throughput in terms of packets/slot that can be received at the AP. This low throughput is the biggest disadvantage of a straightforward, single-packet, contention-based approach.
Another well-known approach for achieving low packet delay in wireless environments is contention-based multi-access with multi-packet reception. See, for example, L. Tong, Q. Zhao, and G. Mergen, “Multipacket reception in random access wireless networks: from signal processing to optimal medium access control,” IEEE Commun. Mag., vol. 39, pp. 108-112, November 2001; Q. Zhao and L. Tong, “A dynamic queue protocol for multi-access wireless networks with multipacket reception,” IEEE Trans. Wireless Commun., vol. 3, pp. 2221-2231, November 2004; and M. K. Tsatsanis, R. Zhang, and S. Banerjee, “Network-assisted diversity for random access wireless networks,” IEEE Trans. Sig. Proc., vol. 48, pp. 702-711, March 2000. In this approach, it is assumed that the AP is capable of simultaneously receiving packets transmitted from up to Nrx users. For example, it can be shown that the maximum number of correctly received packets with Nrx=4 is 2.95 packets/slot, compared to 0.36 packets/slot achievable with slotted Aloha.
Consider multi-packet reception with Nrx=2. Assume that UT-A and UT-B are simultaneously transmitting to the AP. At the AP, the signal transmitted from UT-A is seen as interference when the signal from UT-B is demodulated, and vise versa. In other words, there is a large mutual interference among the signals received from different simultaneously transmitting UTs. Naturally, the data rate that can be reliably received from UT-A depends on the strength of the signal received from UT-B (the stronger the signal received from UT-B, the lower the data rate that can be received from UT-A). Unfortunately, in a wireless environment, the signal received at the AP from each transmitting UT is a function of the channel between each particular UT and the AP. With widely separated UTs (compared to the wavelength of the carrier, which is 15 cm at 2 GHz carrier frequency), the channels between the AP and different UTs are very different. This implies that the data rate than can be received from UT-A depends on the number of UTs that transmit simultaneously with UT-A, and the channel each UT is using. Unfortunately, this information is not known to UT-A when UT-A transmits its packet, and thus the proper data rate cannot be determined. Hence, implementation of a wireless, contention-based, multi-packet system requires a method for each UT to determine the proper transmission data rate such that, with an appropriate receiver at the AP, Nrx packets can be simultaneously decoded at the AP with high reliability.
What is needed in the art is an arrangement and method for contention-based multi-access that overcomes the shortcomings of the prior art. Such an arrangement and method should provide a specific transmission methodology at the UTs and a reception methodology at the AP, which enable the AP to correctly receive Nrx simultaneously transmitted packets with a given degree of reliability (i.e., a small probability that a transmitted packet is incorrectly received at the AP). The present invention provides such an arrangement and method.